1. Statement of the Technical Field
The present invention relates to caching systems, and more particularly to the grouping of object data to achieve caching improvements.
2. Description of the Related Art
Cache memory has become an important structural and programmatic element as a supplement to main memory in a computing system. Cache memory, which typically enjoys enhanced access times when compared to main memory, often is configured to store frequently accessed data items from main memory. When a request is received in the computing system to retrieve data items, the cache can be consulted first to determine whether the requested data item can be retrieved from the cache without requiring a more resource expensive retrieval from main memory. In this way, the proper population of cache memory with data items can produce substantial gains in computing performance.
Careful management of cache memory can be essential to the optimal retrieval of data in a computing system. Though many cache population and replacement methodologies have been implemented through the years, most share the component of determining which data items are most frequently accessed in main memory and ensuring that those most frequently accessed data items are placed in cache memory rather than main memory. Additionally, many conventional caching methodologies co-locate data items in a cache to ensure that related data items are positioned most closely together. In this way, it is more likely that related data items can be retrieved from cache memory quickly in a single cache block.
As an example, in U.S. Pat. No. 6,330,556 to Chilimbi et al., hereinafter, “Chilimbi”, fields within addressable data elements in data structures can be re-ordered to improve the efficiency of cache line access. Specifically, data structures such as a class can be partitioned into heavily referenced and less heavily referenced portions. The partitioning can be based upon profile information regarding field access counts with indirect addressing used to reference the less heavily referenced partitioned class. A class co-location scheme subsequently can be used to ensure that temporally correlated classes are placed near each other in cache blocks.
Similarly, in U.S. Pat. No. 6,360,361 to Larus et al., hereinafter, “Larus”, fields which are individually addressable data elements in data structures can be reordered to improve the efficiency of cache line access. Temporal data regarding the referencing of such fields can be obtained and a tool can be used to construct a field affinity graph of temporal access affinities between the fields. A first pass greedy algorithm thus can be used in processing the affinity graph to combine high affinity fields in the same cache line or block. Finally, in U.S. Pat. No. 6,594,678 to Stoutamire et al., hereinafter “Stoutamire”, objects in memory can be re-arranged according to the frequency of access in memory of one or more fields associated with the object.
In each of Chilimbi, Larus and Stoutamire, the frequency of access of data fields has been established as the sole criteria for determining which data fields to co-locate within one another in cache memory. While substantial performance improvements can be realized from the methodologies of Chilimbi, Larus and Stoutamire, the efficiencies of each are achieved solely through co-locating data fields based upon a single criteria—access count—identified though a single analysis. Oftentimes, however, a one-time analysis of object code based upon a single criteria for configuring the object code for cache co-location can fail to achieve an optimal result. Consequently, to limit the co-location of data fields based upon a single criterion in a single analysis, whether static or dynamic, can result in a less than optimal arrangement.